Аутобуске руте
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,5 s | 64 Mb | стандардни излаз | стандардни улаз |
Познате су руте аутобуса у једном граду. Напиши програм који одређује најмањи број вожњи аутобусом потребан да се стигне од дате почетне до дате завршне станице.
Улаз
Са стандардног улаза се уноси број аутобуса n (1≤n≤105). Наредних n редова описује руте тих n аутобуса. За сваку руту је наведен број m (1≤m≤105) станица дуж те руте, а затим и m различитих редних бројева који представљају станице дуж руте. Аутобуси дуж руте пролазе у оба смера. Укупан број различитих станица на свим рутама није већи од 105, а укупан збир бројева свих станица на свим рутама није већи од 5⋅106. У последњем реду се налазе редни бројеви две станице – почетне и крајње.
Излаз
На стандардни излаз исписати минимални број вожњи потребан да се стигне са почетне до крајње станице. Ако није могуће стићи, исписати -1.
Пример
Улаз
2 3 1 2 7 3 3 6 7 1 6
Излаз
2
Објашњење
Најбоље је на станици 1 се укрцати на први аутобус, ићи до станице 7 и тамо прећи на други аутобус који ће нас одвести до станице 6.
Морате бити улоговани како бисте послали задатак на евалуацију.